1. Field of the Invention
This invention relates to an interconnected, distributed communication system (xe2x80x9cnetworkxe2x80x9d) and more particularly to a structured network of modular switches that is backward compatible with existing broadcast resolution protocols (xe2x80x9cARPsxe2x80x9d) used to find an internet protocol (xe2x80x9cIPxe2x80x9d) identification address of a targeted termination device and its relation to one or more end switch identification addresses within the structured network. Knowing an end switch address, a data packet targeted for that switch (and ultimately to the termination device) need only perform a single mapping or translation operation when transferring a packet to one of several termination devices which might be linked to the structured network.
2. Description of the Related Art
A communication network is generally regarded as an interconnected set of subnetworks or subnets. The network can extend over localized subnets as an intranet, or can extend globally as an internet between one or more intranets. A communication network can therefore forward data within a localized network between termination devices extending to almost anywhere around the world. The termination devices include any data entry/retrieval system (e.g., telephone or computer), and a network includes a local and/or global interconnection of termination devices configured on one or more subnets.
The basic underpinnings of network operation is the various protocols used to communicate between termination devices. A popular foundation for those protocols is the Open System Interconnect (xe2x80x9cOSIxe2x80x9d) model. Using that model or a derivative thereof, protocols can be developed which work in concert with each other. A popular communication protocol includes the Transmission Control Protocol (xe2x80x9cTCPxe2x80x9d) and the Internet Protocol (xe2x80x9cIPxe2x80x9d). Protocols such as TCP/IP determine how the termination devices will communicate with each other over a network configured with or without internet connection.
Many popular protocols including TCP/IP deliver data across the network in the form of a packet. Each packet of a particular message may be sent across different routes of the network at the same time and then reassembled at the proper termination device. In order to ensure the packets are properly received, certain layers of the OSI protocol stack will wrap the data before the packet is sent across the network. For example, TCP can divide data into segments which are then placed into, for example, IP datagrams having a header which includes the IP address of the originating and receiving termination devices. The IP datagram and header is, therefore, a wrapped IP which gets further wrapped when transferring the IP wrapper from the network layer to the data link and physical layers. For example, the IP datagram can be further wrapped using a Point-to-Point Protocol (xe2x80x9cPPPxe2x80x9d), a popular such protocol being that which follows the Ethernet specification at the physical layer. Thus, it is not until the IP has been wrapped possibly several times will be TCP be forwarded across the network.
Coupled between subnets of a network are various classes of devices, including bridges, routers, and switches. Bridges and switches for the most part operate primarily in hardware and within the domain of the data link layer. Legacy routers, on the other hand, operate within the network layer and can be programmed and reconfigured to intelligently forward packets across the network according to the most optimal routing path. Although the distinction has become somewhat blurred with modern day network layer switches and bridges, it is still the primary intent that a switch and bridge be employed mostly in hardware. Based on configuration of the switch or bridge, all data packets received by a particular input port are routinely sent to any particular output port or ports. This operation can be quickly repeated each time a packet is received.
While switches are relatively fast and can send data from an input port to an output port with very little delay or lag time, switches do not have the capability to adapt to change in traffic conditions as do routers. Because routers can easily adapt to avoid traffic bottlenecks, routers employ look-up tables and fairly complex routing algorithms. Typical routers are based on a packet processor. The processor can be programmed to determine the most optimal connection between input and output ports of the router. Coupled to the processor is a memory bus and associated system memory, whereby routing tables can be stored in the system memory and are periodically fetched by the processor whenever a routing decision is to be made. Thus, when a packet is received on one port of the router, the processor will execute a look-up operation by fetching the appropriate table information from system memory. Most routing tables are dynamic, in that they constantly change as network traffic and conditions change, so that the processor can interconnect the ports in a way that is most efficient at that time. Dynamic routing tables can be built and re-built using various routing protocols, popular such protocols include Routing Information Protocol (xe2x80x9cRIPxe2x80x9d) and Exterior Gateway Protocol (xe2x80x9cEGPxe2x80x9d).
Periodically programming the routing tables may mean that one router on a network will not know the location of the physically closest router or its placement within the network. The router will simply route based on its existing routing table and the resulting look-up outcome. Such a system can be considered a non-relative or non-deterministic router topography. Non-deterministic routers tend to rely on the number of hops (i.e., the number of routers or gateways) when determining the most optimal routing path. Thus, while a router may know the number of additional routers on a given path, it does not necessarily know or have a link to the identity of those routers.
In most modern networks, a packet will travel more than 10 or 20 hops before arriving at its destination. As defined herein, a hop is equivalent to a traversal of a router or address translator. More specifically, a hop is defined as an operation that invokes a look-up or translation operation. When traveling across a network, a packet may be sent across numerous look-up or translation tables, and also through numerous switches, before arriving at its destination. It is generally recognized that transmission latency is lessened, and transmission bandwidth increased, if the number of hops is reduced. Therefore, it is desirable that the number of hops from one termination device to another termination device be minimal. This is due, in part, to the time-consumptive look-up (or address translation/modification) procedure performed by each router. Furthermore, since a particular router will not necessarily know the placement of all other routers of a network, each look-up table must include identification numbers or addresses for each of the other routers within the networkxe2x80x94even those not within the optimal routing path. The destination address is compared against each of those identification numbers for each routing operation. If a network is quite large, the access times needed to perform a look-up from the packet processor to the system memory can be correspondingly long.
This problem is compounded with the advent of high speed networks of one gigabits per second (Gb/s) or higher. Look-up techniques needed to render forwarding decisions on rather large look-up tables drastically reduces the benefits of using high speed networks. Many termination devices use high speed physical media, such as Ethernet. Moreover, subnet loops which interconnect localized devices can use even higher speed signals such as, for example, Synchronous Optical Networks (xe2x80x9cSONETsxe2x80x9d).
If the IP packets enter the input port of a router more quickly than that router can process those packets, the packets are sent to an input queue. The router processes packets from the queue in the order in which they are received. If the number of packets received exceeds the capacity of the queue, packets may be lost and may need to be resent. If the comparison between the IP destination and the routing table takes a significant amount of time, then it may be likely that numerous packets may be lost. Frequency of lost data would increase when bursts of data are being sent. The time needed to re-send packets deleteriously hinders the overall throughput of the network.
It would be of benefit to introduce an improved switch having switching speeds of a conventional switch yet also having the adaptability of a router. The improved switch would avoid the throughput constraints of a conventional packet processor and system memory interface and, more importantly, the detriments of an extensive look-up table. The desired switch would be even more beneficial if it could maintain backward compatibility with the OSI model, protocols of that model, and address resolution used by various Address Resolution Protocols (xe2x80x9cARPxe2x80x9d). Still further, the improved switch should desirably be used in an overall network that is deterministic as to the relative placement of each switch within that network. Thus, the switch could determine if it should wrap (or strip) incoming packets as an end switch or should pass-through packets as an intermediate or pass-through switch, both switches advantageously performing those functions with minimal time delay.
The problems outlined above are in large part solved by a structured network, an enabling distributed routing mechanism, an addressing mechanism used within that network, and forwarding/directing devices (xe2x80x9cmodulesxe2x80x9d) topologically related to one another based on their position within the network. The modules, due to an awareness of their position or location with respect to the structured network, allow adaptive fast forwarding of packets across the network. The modules represent an improvement over conventional switches and/or routers. Instead of statically routing packets in the same manner each time, as in conventional switches, the modules include some features of conventional routers, yet without the detriments of routers. The modules can forward and/or direct packets of data relatively fast (similar to conventional switches), and can dynamically change the forwarding path based on activity within the network. For sake of brevity in its description, the modules perform a hybrid of a switch/route function and are henceforth referred to as switches based on the speed at which they forward packets of data, and that they perform a selection function applicable to switches in general. However, it is recognized that the present switches are altogether dissimilar from conventional switches, and are also dissimilar from conventional routers.
The network can be made up of numerous switches extending between termination devices. Each switch performs fast deterministic switching of packets across the network based on conditions of the network. The network can be placed within only a portion of a conventional network, a subnet of which is coupled to one or more termination devices. Regardless of where it is configured, the present network includes one or more topological levels of switches that are structurally related to one another. Each switch within the network is assigned a unique identification number possibly corresponding to the hierarchical level of the network topography that can be ascertained within a given field attributed to that level. For example, the most significant field of bits may be allocated to the highest hierarchical level of switches, followed by the next most significant field allocated to the next highest level of switches. With each level of hierarchy, structure is provided. Structure is also provided within each level. The switches are organized according to some predetermined structure within a given hierarchical level which is reflected in the field of the identification number corresponding to that level. Distributed routing can therefore be achieved by comparing a destination address of the wrapped data packet with identification numbers of those hierarchical levels depending on the location of the switch receiving the incoming packet. Switches direct/forward data packets by determining the direction of flow of the incoming packet based on comparing (or decoding) the destination address of the packet with the relative position of the switch indicated by the switch""s identification number. As the result of this direction/forwarding operation, traditional routing methods are eliminated. Also, decoding operations eliminate routing in what was determined, at a higher hierarchical level, to be an unused path. Decoding within lower levels can be restricted only to those switches that the higher levels point toward. Moreover, decoding can be accomplished in a fairly rapid manner and need not occur if a comparison at the higher level will direct the packet to another branch of lower level switches. In this manner, each switch is assigned an identification number based on its relative position within the network. Accordingly, the structured network can be thought of as having a relative or deterministic routing topography absent the detriments of conventional routers. Hence the deterministic routing acts as a distributed router. Instead of performing routing functions at every node in the network, the distributed router performs incremental routing functions at every node and the data forwarding function is achieved across the entire network.
Within the structured network is at least one switch and, preferably, numerous switches interconnected to form an intranet, an internet, or a combination of both. The switches can be classified as an end switch, a pass-through switch, or an intermediate switch. The end switches are those that are configured adjacent termination devices and are used to perform protocol wrapping functions as packets of data enter the structured network, or strip protocol used by the structured network when packets exit the network. The end switches also perform a routing function similar to intermediate switches or pass-through switches. The end switches, intermediate switches, and pass-through switches can be configured in hardware to be substantially the same, with only the programmed function being different based on where within the network the switches are placed. Each switch includes a minimum of one bi-directional port and a traffic manager which controls the port, or ports. The number of ports is scalable in that there may be one or more input ports and one or more output ports arranged in various configurations with the traffic manager deciding which packet received on an input port will be forwarded to which of the various output ports. The traffic manager includes a decoder and various buffers. The decoder performs a comparison between the destination address and the identification number of that switch based on the position of that switch within the overall structured network. The comparison and decision are based on the comparison represented as an incremental step in the distributed routing function (data forwarding function) of the network.
A shared or distributed buffer may be placed within the data flow path to receive a packet and to forward that packet to the appropriate output port based on the destination address. Instead of forwarding the data into a buffer, the data can be selectively forwarded across one or more bypass conductors coupled in parallel across the buffer. Thus, a module which forms an intermediate switch or end switch can be configured with bypass operations applicable to a pass-through switch or a pass-through node, and the bypass paths are used to reduce latency in the switches. The buffer can also be contained with an end switch and configured with control information. Through a series of read or fetch operations, the buffer may be used to wrap an incoming packet and associated address with control information as well as an originating address of the end switch. The fetch operations occur in rapid succession from a traffic controller of the traffic manager.
The structured network is one that is completely compatible with protocols currently used in, for example, the OSI model. Specifically, a conventional address resolution protocol can be used to determine the location of a destination termination device by comparing an address (e.g., IP address) broadcast over the structured network. Once the destination termination device is found, the end switch within the structured network that is linked to the termination device can also be found. The end switch nearest the destination termination device can be thought of as an exit end switch whose identification number is known. When packets of information are to be sent to the destination termination device, it is known that those packets will be targeted to the exit end switch and forwarding operations are achieved through the hierarchical decode operation using a series of compare operations within only select switches of certain hierarchical levels. The entry end switch adjacent the entry termination device will wrap the physical media packet with an originating identification number of the entry end switch. The packet can then be forwarded throughout the structured network without having to perform any look-up operations.
When the packet arrives upon the exit end switch, control information of the structured network is stripped from the packet and a relatively small mapping table may be used to forward the packet to a relatively small number of destination termination devices selectively linked to the exit end switch. If, however, only one termination device is linked to the exit end switch, then mapping is not needed and consequently, no translation need occur. The comparison or translation performed at the exit end switch occurs to bridge the gap between the structured network and any external protocol or domain, hence the translation is a full comparison. For example, a full 32-bit random IP address can be used to look-up a 48-bit Ethernet address of the termination device. Across the structured network, instead of having to make a comparison of an incoming address against all switch identification numbers, the deterministic network hereof need only compare a field of bits within a certain level of the network depending on where the entry end switch is located within the hierarchical level. Further comparisons are performed only on a field-by-field basis, each time lessening the number of fields needing comparison. In instances where the structured network is quite small, comparison may be required only on a single field to determine, for example, whether to forward the packet left or right around a single loop.
Only a fraction of the overall number of switch identification numbers are compared against the destination address and, more importantly, no look-ups are needed in the forwarding operations. In particular, a self-compare operation occurs within each switch""s decoder along the forwarding path. A result of the self-compare is a switch within one level pointing to another switch in another level based solely on the decode operation. Only a small mapping operation may be needed by the exit switch when identifying which of the various destination termination devices connected to the exit end switch will receive data. The number of termination devices connected to the exit switch is significantly smaller than the sum total of switches or nodes within a network. Importantly, the extent of the translation table associated with the exit end switch is local to that switch""s location within the network node and to the domain of the termination devices known to be connected to it. The mapping table is completely independent of the interior structured network and is based solely on a known relationship between an exit end switch and termination devices connected thereto. This allows the mapping table to be static for the most part. Any changes to this table is completely localized and does not require updating of other nodes and/or switches within the structured network.
The addressing mechanism thereby targets the exit end switch after performing a conventional address resolution protocol. When forwarding data back from the exit end switch via the termination device connected thereto, the forwarded data can be directed to the entry end switch via the entry end switch identification number placed on the packet received by the destination termination device. Accordingly, in a reply to the originating packet, no look-ups are needed. Only a relatively small mapping operation may be needed when forwarding the reply outside of the structured network (i.e., when forwarding the reply packet back to the originating termination device). Thus, if more than one termination device is linked to the end switches, only one mapping occurs when routing packets of data from the structured network, either to the destination termination device or back to the origination termination device. All routing functions are achieved by a field-by-field comparison, much like a distributed routing operation.
The entry and exit end node identification numbers may be configured or reconfigured such that they are recognizable to the termination devices connected thereto. For example, if the network is to receive Ethernet-based packets, then the entry and exit end switches are configured with identification numbers that are within the Ethernet address range. Since the network is structured, with successive nodes and/or switches being recognizable to each other, all other switches in the network are in the same addressing domain. This allows for replacement of the termination device address with the identification number of the entry/exit end switch proximate to that device. Importantly, the termination device which forwards the destination address can now recognize that the address (e.g., Ethernet address) of the termination device at the opposing end of the network is at the Ethernet address of the end switch connected to that device.
At the entry end switch, the incoming termination device address (e.g., Ethernet address) can be replaced with the Ethernet address of the entry end switch (i.e., the entry end switch identification number) in the data packet. The targeted or destination termination device recognizes that the data originating from the incoming termination device is that of the entry end switch and now knows to forward all replies to the identification number, or address, of that switch. When the reply reaches the originating entry end switch (i.e., exit end switch for the reply), the next highest level of protocol (e.g., IP address) address is used to identify 1 of possibly N termination devices attached to the entry end switch. This is a fairly simply reply translation, and the only look-up needed during the reply operation. The relatively simple look-up, like the request look-up preferably involves a small, static look-up table local only to the end switches. The only entries within the table are the next protocol level (e.g., IP within the protocol stack) relative to the physical protocol level (e.g., Ethernet) address mapping.
A traditional hop used by conventional routers may involve replacement of a lower level (e.g., Ethernet) source and destination address of the packet with the next destination Ethernet address. The next destination Ethernet address (or hop address) is determined by the routing table within the convention router, said table is dynamically managed by the network. The present switches replace the source address at the entry and destination address at the exit end switch, but not for purposes of xe2x80x9chopxe2x80x9d routing. Instead, the present switches merely allows for more than one termination device per entry-exit switch. If only one termination device is coupled to an end switch, then address translation, look-up or hop is not needed. Simply a 1-to-N or N-to-1 mapping occurs. In a conventional sense, a hop is not used. Instead, the exit end switch simply performs a mapping of 1-to-N when exiting the structured network, provided of course that N termination devices are present. If only one termination device is present, or if routing functions are present in multiple termination devices, then the end switches need not perform any mapping whatsoever.
The traffic manager within a particular switch can be combined with other traffic managers of other switches to form a modular switch arrangement having any of numerous input and output port configurations. Additionally, each input port of the modular-connected traffic managers can receive data at differing speeds and with differing formats or protocols. The modular connection of traffic managers can form an overall switch that is compatible with dissimilar protocols and transmission speeds for use in any desired network connection or multiple network connections. For example, the input port attributed with a first traffic manager can receive 1.0 gigabit Ethernet information, whereas another input port attributed with another traffic manager can receive 5.0 gigabit fiber optic information. Thus, each traffic manager includes buffers which not only receive and temporarily store packets, but also are used to interface with differing transmission speeds of packets forwarded to the input port and packets exiting from the output port.
Within a modularized, interconnected set of traffic managers and associated ports, is a local bus which couples a control processor to each of the scaled traffic managers. A single control processor can therefore be used to receive diagnostic, monitoring, and control information necessary to perform those functions upon one or more of the inter-linked traffic managers. The diagnostic, monitoring, and control information can be sent across an optical fiber, a copper conductor, or a wireless medium to the control processor which will then forward the appropriate control signals across the local bus. The diagnostic, monitoring and control (xe2x80x9cDCMxe2x80x9d) signals may be transmitted to the control processors and traffic managers using the same network, resulting in an in-band signally or more optimally, the processors and traffic managers can use the DMC signal for out-of-band signaling.
For example, the traffic managers can be programmed or configured when they are installed within the network and reconfigured from a centralized location at a later date via a transceiver and the control processor. Reconfiguration performed in conjunction with self-testing operations can determine historical traffic congestion areas of the network to allow the network to adapt and reroute packets away from the congested areas. Rerouting can occur either by configuring the traffic managers in those suspected areas or broadcasting a reconfiguration signal from the centralized locations. Importantly, however, the DMC signals sent to the control processor, and the control processor and local bus interface can remain entirely outside the data flow path. Data flow does not depend on, and therefore is not slowed by, access to and from the control processor. Once the control processor has performed its function, further access thereto is not needed.
According to one embodiment, a communication network is provided. The communication network is a structured network with distributed routing function comprising a plurality of interconnected switches. To enable distributed routing, each switch includes an identification number bifurcated into several groupings of bits, or fields. A first grouping of bits helps identify a first switch for receiving data of the network prior to a second grouping of bits identifying a second switch for receiving data from the first switch. The first switch can be considered as being within a first hierarchical level and the second switch can be considered within a second hierarchical level. The first and second hierarchical levels are not necessarily the highest level and second to highest level, but are simply two levels within the overall hierarchy. A decoder within the first switch can compare an address of the forwarded data or packet with the first grouping of bits if the address originates from a switch within a hierarchical level dissimilar from the first hierarchical level. Thus, the originating address is either in a hierarchical level above or below the first hierarchical level. The same can be said regarding a decoder within the second switch and its comparison function.
The first switch, or first set of switches within the first level, are connected upon or between a first set of loops that are associated with a first set of network nodes. Likewise, the second switch, or second set of switches within the second level, are connected upon or between a second set of loops that are associated with a second set of network nodes. According to one example, at least one network branch may be terminated at both ends by a switch within the first set of switches and a switch within the second set of switches to enable coupling of the first set of network nodes to the second set of network nodes to provide a selectable routing path. The network nodes and network branches can be thought of as extending at least partially between terminating devices to form a data flow path therebetween.
According to another embodiment, the structured network can be modularized. The modular network includes a set of switches interconnected across at least a portion of the network. A single control processor is also provided having a local bus extending between the control processor and each of the set of switches. The local bus is adapted to receive from the control processor diagnostic, monitoring or control signals. The control signals may include signals used to, e.g., reconfigure an identification number for at least one of the set of switches to change routing of data or packets through those set of switches. The control processor can receive wireless or wired (optical or solid conductor) communication from a transceiver placed remote from the control processor.
According to still another embodiment, the structured network may include more than three nodes and three branches. Only one switch within one node may be used to perform a single 1-to-N address mapping as the data traverses the entire routing network and is forwarded to the selected one of N termination devices with no routing look-ups in the interim. The mapping can be performed by a selection device, such as for example a multiplexer or router, and the mapping is used to select only between multiple termination devices, and not between ensuing nodes and/or switches within the network.
An addressing mechanism is contemplated for use within the network. The network thereby includes an entry end switch and an exit end switch. Both entry and exit end switches are selectably may be coupled to a plurality of termination devices, one of which is an exit termination device or destination termination device to which one or more packets are currently being sent. Between the exit and entry end switches are a plurality of intermediate switches. The packet is compiled by the entry end switch to contain a destination address of the exit end switch. The packet is forwarded through the plurality of intermediate switches, with each intermediate switch having an identification number which points the packet to a successive one of the plurality of intermediate switches and finally to the exit end switch. The exit end switch performs the single mapping translation in order to forward the packet solely from the exit end switch to the exit termination device. Thus, while addressing within the structured network may be unique to that network, addressing outside of that network remains compatible with existing OSI layer protocols applicable to TCP/IP, SONET, and/or Ethernet, for example.
Yet further, a method is contemplated for routing data. The method includes compiling a packet comprising a destination address of the exit end switch and a source address of the entry termination device, and thereafter forwarding the packet from the entry termination device to the entry end switch. While maintaining the destination address, updating the source address to the address of the entry end switch while forwarding the packet from the entry end switch to the exit end switch, exclusive of look-up operations in the interim. While maintaining the source address, updating the destination address to the address of the exit termination device while routing the packet from the exit end switch to the exit termination device.
Before compiling the packet, an address resolution protocol may be broadcast from the entry termination device to the entry end switch, and thereafter to the exit end switch for finding the location of the exit end switch relative to the exit termination device. Within each switch is a traffic manager. The traffic manager may include a traffic controller which dispatches a series of read operations to memory coupled within a data flow path between the input and output ports of the switch. Thus, the memory may include control information placed therein during a configuration cycle. The memory may also temporarily store packets of data dispatched from the input port. The traffic manager reads the control information and the packets of data in a predefined sequence so as to compile a wrapped packet that can then be forwarded to the output port.
The memory comprises any media which can receive packets of data and thereafter transfer those packets. The memory may involve a buffer, comprising semiconductor memory, wherein the memory is coupled to a bus across which packets of data are forwarded. The memory is responsive to a control signal forwarded across a bus separate from the bus that transfers packets. Thus, the bus represents a routing path of the network. The traffic controller works in conjunction with memory, similar to a compiler, for reading packets of data from memory and wrapping that data with control information stored in another section of the memory. In addition to it managing traffic flow through the switch, the traffic controller also functions to control the allocation of various resources such as ports, bypass paths and buffers within the switch.
In addition to the memory (or buffer) a conductor may be coupled in parallel across the buffer. A configuration register associated with the traffic manager may be programmed to select routing of the data flow path across either the buffer or the conductor depending on the availability of the output port.
The method for wrapping a packet of data may therefore include temporarily storing a packet of data in memory located within the flow path of the packet. A set of read operations can be dispatched to memory for reading various addresses (destination and origination addresses), control information, and the temporarily stored packets, in order to form at least a portion of a wrapped data packet.